package org.ala.everyday;

import java.util.Arrays;

/**
 * 一个音乐会总共有 n 排座位，编号从 0 到 n - 1 ，每一排有 m 个座椅，编号为 0 到 m - 1 。你需要设计一个买票系统，针对以下情况进行座位安排：
 *
 * 同一组的 k 位观众坐在 同一排座位，且座位连续 。
 * k 位观众中 每一位 都有座位坐，但他们 不一定 坐在一起。
 * 由于观众非常挑剔，所以：
 *
 * 只有当一个组里所有成员座位的排数都 小于等于 maxRow ，这个组才能订座位。每一组的 maxRow 可能 不同 。
 * 如果有多排座位可以选择，优先选择 最小 的排数。如果同一排中有多个座位可以坐，优先选择号码 最小 的。
 * 请你实现 BookMyShow 类：
 *
 * BookMyShow(int n, int m) ，初始化对象，n 是排数，m 是每一排的座位数。
 * int[] gather(int k, int maxRow) 返回长度为 2 的数组，表示 k 个成员中 第一个座位 的排数和座位编号，这 k 位成员必须坐在 同一排座位，且座位连续 。换言之，返回最小可能的 r 和 c 满足第 r 排中 [c, c + k - 1] 的座位都是空的，且 r <= maxRow 。如果 无法 安排座位，返回 [] 。
 * boolean scatter(int k, int maxRow) 如果组里所有 k 个成员 不一定 要坐在一起的前提下，都能在第 0 排到第 maxRow 排之间找到座位，那么请返回 true 。这种情况下，每个成员都优先找排数 最小 ，然后是座位编号最小的座位。如果不能安排所有 k 个成员的座位，请返回 false 。
 *
 *
 * 示例 1：
 *
 * 输入：
 * ["BookMyShow", "gather", "gather", "scatter", "scatter"]
 * [[2, 5], [4, 0], [2, 0], [5, 1], [5, 1]]
 * 输出：
 * [null, [0, 0], [], true, false]
 *
 * 解释：
 * BookMyShow bms = new BookMyShow(2, 5); // 总共有 2 排，每排 5 个座位。
 * bms.gather(4, 0); // 返回 [0, 0]
 *                   // 这一组安排第 0 排 [0, 3] 的座位。
 * bms.gather(2, 0); // 返回 []
 *                   // 第 0 排只剩下 1 个座位。
 *                   // 所以无法安排 2 个连续座位。
 * bms.scatter(5, 1); // 返回 True
 *                    // 这一组安排第 0 排第 4 个座位和第 1 排 [0, 3] 的座位。
 * bms.scatter(5, 1); // 返回 False
 *                    // 总共只剩下 2 个座位。
 *
 *
 * 提示：
 *
 * 1 <= n <= 5 * 104
 * 1 <= m, k <= 109
 * 0 <= maxRow <= n - 1
 * gather 和 scatter 总 调用次数不超过 5 * 104 次。
 *
 * @author ala
 * @date 2024-09-28 00:44
 */
public class Q2286 {

    public static void main(String[] args) {
        int n = 5, m = 9;
        BookMyShow bms = new BookMyShow(n, m);
        System.out.println(bms.scatter(2, 2));
        System.out.println(Arrays.toString(bms.gather(7, 2)));
        System.out.println(Arrays.toString(bms.gather(4, 1)));
        System.out.println(Arrays.toString(bms.gather(6, 2)));
        System.out.println(bms.scatter(2, 1));

    }

    static class BookMyShow {
        //  N行M列
        int N, M;

        public BookMyShow(int n, int m) {
            this.N = n;
            this.M = m;
            initBySegmentTree();
        }

        public int[] gather(int k, int maxRow) {
            return gatherBySegmentTree(k, maxRow);
        }

        public boolean scatter(int k, int maxRow) {
            return scatterBySegmentTree(k, maxRow);
        }


        /******************************************************************************************
         *  线段树
         *
         *  1）按照规则，每行的分配一定是从左往右连着分配，中间不会有空隙。且优先找排号最小的排
         *  2）对于 gather，需要找到 [0, maxRow] 之间，下标最小且空位超过 k 的那一排
         *  3）对于 scatter，需要先判断 [0, maxRow] 的空位总额是否 >= k
         *      若是：从 0 到 maxRow 贪心分配即可
         *      若否：直接false
         *  4）需要一个
         *  4）需要一个区间极小线段树，用于 gather 找到下标最小且空位超过 k 的排号
         *      线段树中记录当前最小
         *  5）需要一个区间和线段树，用于 scatter 查询区间 [0, maxRow] 的空位总额是否 >= k
         *  6）需要记录当前全满下标，该下标（含自己）往左都是满的（没有空位），用于 scatter 分配座位
         *
         ******************************************************************************************/
        protected int[] pos;
        protected SegmentTreeMin stm;
        protected SegmentTreeSum sts;
        protected int minFull = -1;
        protected void initBySegmentTree() {
            pos = new int[N];
            stm = new SegmentTreeMin(N, M);
            sts = new SegmentTreeSum(N, M);
        }
        protected int[] gatherBySegmentTree(int k, int maxRow) {
            int i = stm.query(maxRow, k);
            if (i == -1) {return new int[0];}
            int[] res = new int[] {i, pos[i]};

            pos[i] += k;
            stm.incr(i, k);
            sts.incr(i, k);

            return res;
        }
        protected boolean scatterBySegmentTree(long k, int maxRow) {
            long d = sts.query(maxRow);
            d = (maxRow + 1l) * M - d;
            if (d < k) {return false;}

            for (int i = minFull + 1 ; i <= maxRow ; i++) {
                long _d = Math.min(M - pos[i], k);
                k -= _d;

                pos[i] += _d;
                stm.incr(i, _d);
                sts.incr(i, _d);

                if (pos[i] == M) {
                    minFull = i;
                }
                if (k == 0) {break;}
            }
            return true;
        }

        static class SegmentTreeMin {
            long[] tree;
            int N, M;
            public SegmentTreeMin(int N, int M) {
                this.N = N;
                this.M = M;
                tree = new long[2 << (32 - Integer.numberOfLeadingZeros(N))];
            }
            public void incr(int i, long k) {
                incr(i, k, 0, N - 1, 1);
            }
            private void incr(int i, long k, int s, int t, int p) {
                if (s == t) {
                    tree[p] += k;
                    return;
                }
                int m = s + ((t - s) >> 1);
                if (i <= m) { incr(i, k, s, m, p << 1); }
                else { incr(i, k, m + 1, t, (p << 1) + 1); }
                tree[p] = Math.min(tree[p << 1], tree[(p << 1) + 1]);
            }
            public int query(int i, int k) {
                return query(0, i, k, 0, N - 1, 1);
            }
            private int query(int l, int r, long k, int s, int t, int p) {
                long _k = M - tree[p];
                if (_k < k) {
                    return -1;
                }
                if (s == t) {return s;}
                int m = s + ((t - s) >> 1);
                if (l <= m) {
                    int res = query(l, r, k, s, m, p << 1);
                    if (res != -1) {return res;}
                }
                if (r > m) {
                    int res = query(l, r, k, m + 1, t, (p << 1) + 1);
                    if (res != -1) {return res;}
                }
                return -1;
            }
        }
        static class SegmentTreeSum {
            long[] tree;
            int N, M;
            public SegmentTreeSum(int N, int M) {
                this.N = N;
                this.M = M;
                tree = new long[2 << (32 - Integer.numberOfLeadingZeros(N))];
            }
            public void incr(int i, long k) {
                incr(i, k, 0, N - 1, 1);
            }
            private void incr(int i, long k, int s, int t, int p) {
                if (s == t) {
                    tree[p] += k;
                    return;
                }
                int m = s + ((t - s) >> 1);
                if (i <= m) {
                    incr(i, k, s, m, p << 1);
                } else {
                    incr(i, k, m + 1, t, (p << 1) + 1);
                }
                tree[p] = tree[p << 1] + tree[(p << 1) + 1];
            }
            public long query(int i) {
                return query(0, i, 0, N - 1, 1);
            }
            private long query(int l, int r, int s, int t, int p) {
                if (s >= l && t <= r) {
                    return tree[p];
                }
                int m = s + ((t - s) >> 1);
                long sum = 0;
                if (l <= m) {
                    sum += query(l, r, s, m, p << 1);
                }
                if (r > m) {
                    sum += query(l, r, m + 1, t, (p << 1) + 1);
                }
                return sum;
            }
        }
    }
}
